Since the advent of computers capable of running several programs concurrently, data security has been an important issue in system design. When different programs share the same hardware resources it is essential to ensure that they are not able to access or alter each other""s data unless sharing is explicitly allowed by the programmer. Data security within a single program is also desirable to the developer, as it eliminates potential sources of program errors.
Traditionally, inter-process security has been addressed by maintaining a per-process page-table providing a translation from virtual address to physical location. This gives each process a separate address space and allows the operating system to ensure that it is impossible for data of a process to be inspected or corrupted by other applications. While such an approach is functional, there are three main objections to it. First, a process dependent address translation mechanism dramatically increases the amount of processor state associated with a given process. This makes context switching correspondingly slower, thus increasing system overhead and reducing efficiency. Second, data can only be shared between processes at the page granularity. Finally, this mechanism does not provide security within a single context; a program is free to create and use invalid pointers.
The idea of using capabilities for addressing first appeared formally in a paper by Jack B. Dennis, Earl C. Van Horn, xe2x80x9cProgramming Semantics for Multiprogrammed Computations,xe2x80x9d Communications of the ACM, Vol. 9, No. 3, March 1966, pp. 143-155, and further developed by R. S. Fabry, xe2x80x9cCapability-based addressing, Communications of the ACM,xe2x80x9d 17(7):403-12, July 1974. In concept, each capability specifies a segment of memory and a set of permissions detailing the operations permitted upon that region. Fabry""s scheme represents each capability as a set of permissions and a segment-identifying unique ID. A hash table keyed on UIDs contains segment base and bounds information; a small associative cache preserves mappings for the most recently accessed segments. Fabry""s approach is thus efficient when using small numbers of segments but inappropriate to a system in which every independently-allocated object is placed in its own segment.
A number of early capability systems used centralized tables mapping from capabilities to segment addresses; several are described in Henry M. Levy, xe2x80x9cCapability-based computer systems,xe2x80x9d Digital Press, 1984. While some of these machines segregate non-capability data from capabilities in distinct segments, the evolutionary trend is clearly toward tagging capabilities in a hardware-recognizable fashion so that they may be freely intermingled with other data.
Most modern capability systems have avoided the centralized table by embedding object addresses directly in the capability representation. We will not attempt to list them all here, but rather to provide a small number of examples representing keypoints in the design spectrum.
In the ORSLA capability-system described in Peter B. Bishop. xe2x80x9cComputer Systems With A Very Large Address Space and Garbage Collection,xe2x80x9d PhD thesis, Massachusetts Institute of Technology, May 1977 a capability contains permissions bit, the address of the first word of an object, and a small size field (5-9 bits). With each memory reference, an offset is added to the base address in the capability.
The first bit of the size filed distinguishes small and large objects. For small objects, the remaining bits simply represent the size in words. For large objects, the remaining bits are divided into exponent and mantissa components, the exponent defining a block size and the mantissa defining a number of blocks in a segment. This floating-point number can describe (at coarser granularities) much larger segments than can an integer represented with the sane number of bits. Rather than setting the value of the size field to be slightly larger than the number of words in the contained object, ORSLA sets it to be slightly smaller; the object""s precise size is stored in the object itself. When a reference to the last few words of a large object violates the capability""s size field, microcode performs additional memory references to check the precise size stored in the object.
This scheme gives ORSLA precise object bounds at the cost of an extra memory reference for words toward the end of an object. Object allocation is extremely easy in ORSLAxe2x80x94objects may be allocated consecutively by simply advancing a shared allocation pointer.
The Symbolics 3600 Lisp Machine architecture (David A. Moon, xe2x80x9cArchitecture of the symbolic 3600,xe2x80x9d 12th Annual International Symposium on Computer Architecture Conference Proceedings, pages 76-83, 1985) features per-object pointers which directly reference the first word of their target objects. Rather than encoding bounds information in these pointers, however, the object size is encoded in the object""s first word; performing bounds-checking on object references requires an extra memory reference. Note, since a Symbolics pointer contains no permissions bits, it is a fairly degenerate form of xe2x80x9ccapabilityxe2x80x9dxe2x80x94possession of a pointer implies permission to perform any and all operations on its target object.
The M-machine (Marco Fillo, Stephen W. Keckler, William J. Dally, Nicholas P. Carter, Andrew Change, Yevgeny Gurevich and Whay S. Lee, xe2x80x9cThe m-machine multicomputer,xe2x80x9d in Proc. 28th Annual International Symposium on Microarchitecture, pages 146-156, 1995) uses a guarded pointer format (described in Nicholas P. Carter, Stephen W. Keckler and William J. Dally, xe2x80x9cHardware support for fast capability-based addressing,xe2x80x9d in Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VI), pages 319-27, October 1994 and U.S. Pat. No. 5,845,331, which are incorporated by reference in their entireties) to encode permissions, an address, and a segment length descriptor L. The upper bits of the address are fixed, while the lower L bits are mutable by pointer arithmetic; the segment is thus of size and alignment 2L, and the capability may point to any address within it. The base address of a segment may be computed by simply setting the L tower bits to zero, and a user stays within the defined segment so long as the base bits remain unchanged. This scheme requires hardware-recognized (i.e., tagged) capabilities and a small amount of hardware support in the processor to verify bounds information in parallel with performing pointer arithmetic. Notably, it requires neither indirections through a central table, nor the embedding of size information in an object representation.
Two disadvantages of the M-machine approach both arise from the exponentiated segment sizes. First, for an object only slightly larger than some power of two, nearly half of the segment allocated to hold it will be unused; this internal fragmentation both wastes space and means that accesses which overrun the end of the object will not immediately be detected as they will still fall into the segment. Second, due to the strict alignment requirement, a simple allocation strategy based on advancing a pointer may wind up wasting nearly half of memory due to external fragmentation.
In accordance with the present invention, those disadvantages are reduced by defining a memory segment by a block size and a number of blocks in the segment. An index into the memory segment, which identifies the block to which an address of the pointer points, is also included in the pointer representation in order to allow computation of the full bounds of the segment relative to the pointed-to address.
In accordance with one aspect of the invention, a pointer representation within a data processing system comprises a block field which defines a block size and a length field which defines a number of blocks in a segment of memory. An address in the representation points into the segment of memory. A finger field denotes a block of the segment of memory into which the address points.
The pointer representation may further include a permission field which indicates how a process may access data within the segment of memory. A capability field may identify the pointer representation as a capability pointer having bounds and permission defined therein. The representation may bound the segment of memory to the number of blocks indicated by the length field, each block of size 2B a where B is a value defined in the block field.
A base address may be computed from the address in the pointer representation by setting the B least significant bits of the address equal to zero, where B is the block a size, and subtracting a block index indicated by the finger field from the base bits of the address, excluding the B least significant bits.
In order to reduce the required number of bits, the length field may be encoded such that the number of blocks is indicated by adding a defined constant to the value in the length field for all but the smallest range of numbers and the smallest block size.
The pointer representation may further include an increment-only bit, the system excluding negative offsets to the address in the memory representation. The address of the pointer representation may then point to the base address of a memory region within the segment. All portions of the memory segment not within the memory region have addresses less than the address in the pointer representation.
A subsegment within the segment of memory may be defined by a memory representation which includes a block field, length field and finger field, respectively, for each of the segment of memory and the subsegment.